
#include "recursion.h"
#include <iostream>
#include <vector>
#include <string>
#define setbit(x,y)  (x|=(1<<y)) //let the y bit be 1  
#define twosetbit(x,y,z) (x|=((1<<y)|(1<<z)))
#define clrbit(x,y)  (x&=~(1<<y)) //let the y bit be 0
#define twoclrbit(x,y,z) (x&=~((1<<y)|(1<<z)) )
#define reversebit(x,y)  (x^=(1<<y)) //reverse the y bit
#define getbit(x,y)   ((x) >> (y)&1) //get the y bit number begin with the 0 bit
using namespace std;

//double SequenceRecursion1(unsigned long long int Sequence,int CurrentLeft,int CurrentRight,int CurrentLayer,double CurrentLowEnergy,int SequenceLength)
unsigned long long int SequenceLowEnergy;
double currentenergy=1000;
long int count;
void  SequenceRecursion(unsigned long long int Sequence,int CurrentLeft,int CurrentRight,int CurrentLayer,int SequenceLength)
{     
    //cout<<"call";
    #if 1
  int PartCrelation=0;
  int Umin=0;
  int Umax=0;
  int MinMayReachEnergy=0;
  int MinMayReachEnergy1=0;
  int ExceedNSubKEnergy=0;                  //计算  间隔大于n-k部分的能量
  int SumEnergy=0;
    if(CurrentLeft>CurrentRight+2){
      // add
     for(int BigInterval=SequenceLength-1;BigInterval>=CurrentLeft;BigInterval--){
        for(int k=0;k+BigInterval<SequenceLength;k++){
            if(getbit(Sequence,k)^getbit(Sequence,(k+BigInterval))){
                ExceedNSubKEnergy=ExceedNSubKEnergy-2;
            }
            ExceedNSubKEnergy++;

        }
          
            SumEnergy+=ExceedNSubKEnergy*ExceedNSubKEnergy;
            ExceedNSubKEnergy=0;
     }


      //add end int
     // int number1=0;   //
     

        for(int Interval=1;Interval<CurrentLeft;Interval++){
            for(int k1=0;k1<Interval;k1++){
            for(int k=k1;k+Interval<SequenceLength;k+=Interval){
               // number1++;
                if(k<=CurrentRight||(k>=CurrentLeft&&k<SequenceLength)){

               if(k<=CurrentRight&&k-Interval>=0){
                if(getbit(Sequence,(k))^getbit(Sequence,(k-Interval))){
                    PartCrelation=PartCrelation-2;
                }
                PartCrelation++;
               }
              if(k>=CurrentLeft&&k-Interval<=CurrentRight/*&&number1==1*/){    //
                 if(getbit(Sequence,(k))^getbit(Sequence,(k-Interval))){
                    PartCrelation=PartCrelation-2;
                }
                PartCrelation++;
                //number1=0;  //


               }
               if(k>=CurrentLeft&&k+Interval<SequenceLength){                   /////////////

                  if(getbit(Sequence,(k))^getbit(Sequence,(k+Interval))){
                    PartCrelation=PartCrelation-2;
                }
                PartCrelation++;
               }
               

                }

            }  // for k
        }
          


            if(Interval<=CurrentLayer){
                //
                  int ItemNumber=0;
            int LefBit=0,RightBit=0;
            int CalculateN=0;
              for(int temp=CurrentLeft;temp<CurrentLeft+Interval;temp++){
                LefBit=getbit(Sequence,temp);
                for( CalculateN=temp;CalculateN>CurrentRight;CalculateN=CalculateN-Interval){
                    ItemNumber++;



                }
               // ItemNumber--;  //
                if(ItemNumber!=1){
                    RightBit=getbit(Sequence,CalculateN);
                   // ItemNumber--;  //
                    if((RightBit==LefBit)&&(ItemNumber%2==0)){
                       Umin-=ItemNumber;
                    Umax+=ItemNumber; 
                    }
                    if((RightBit==LefBit)&&(ItemNumber%2==1)){
                        Umin=Umin-ItemNumber+2;
                    Umax+=ItemNumber; 
                    }
                    if((RightBit!=LefBit)&&(ItemNumber%2==0)){
                        Umin=Umin-ItemNumber+2;
                    Umax+=ItemNumber-2; 
                    }
                    if((RightBit!=LefBit)&&(ItemNumber%2==1)){
                        Umin-=ItemNumber;
                    Umax+=ItemNumber-2; 
                    }
                    ItemNumber=0;

                }
                else{
                    //ItemNumber--;
                    //Umin-=ItemNumber;  //
                    //Umax+=ItemNumber;  //
                    ItemNumber=0;            //////////zero

                }

              }
            
            }


           if(Interval>CurrentLayer){
            int ItemNumber=0;
            int LefBit=0,RightBit=0;
            int CalculateN=0;
            for(int temp=SequenceLength-1;temp>SequenceLength-Interval-1;temp--){
                if(temp<CurrentLeft){
                    for( CalculateN=temp;CalculateN>CurrentRight;CalculateN-=Interval){
                        ItemNumber++;
                    }
                    if(CalculateN<0)
                    {
                    ItemNumber--;
                   // ItemNumber--;    //
                    Umin-=ItemNumber;
                    Umax+=ItemNumber;
                    ItemNumber=0;
                    }
                    else{
                        //ItemNumber--;    //
                        Umin-=ItemNumber;
                    Umax+=ItemNumber;
                    ItemNumber=0;
                    }

                }
                else{//new else
                LefBit=getbit(Sequence,temp);
                for( CalculateN=temp;CalculateN>CurrentRight;CalculateN=CalculateN-Interval){
                    ItemNumber++;
                 }
            
                if(CalculateN>=0){
                    if(ItemNumber==1){
                        /* Umin-=ItemNumber;
                    Umax+=ItemNumber;*/
                    ItemNumber=0;          ///////////zero
                         
                    }else{
                    RightBit=getbit(Sequence,CalculateN);
                    if((RightBit==LefBit)&&(ItemNumber%2==0)){
                       Umin-=ItemNumber;
                    Umax+=ItemNumber; 
                    }
                    if((RightBit==LefBit)&&(ItemNumber%2==1)){
                        Umin=Umin-ItemNumber+2;
                    Umax+=ItemNumber; 
                    }
                    if((RightBit!=LefBit)&&(ItemNumber%2==0)){
                        Umin=Umin-ItemNumber+2;
                    Umax+=ItemNumber-2; 
                    }
                    if((RightBit!=LefBit)&&(ItemNumber%2==1)){
                        Umin-=ItemNumber;
                    Umax+=ItemNumber-2; 
                    }
                    ItemNumber=0;
                    }

                }
                else{

                    ItemNumber--;
                    Umin-=ItemNumber;
                    Umax+=ItemNumber;
                    ItemNumber=0;

                }
                
                }//new else end
                
            }

            }
           
           

            if(-PartCrelation<=Umin){
                MinMayReachEnergy+=PartCrelation+Umin;
            }
            else if(-PartCrelation>=Umax){
                MinMayReachEnergy+=PartCrelation+Umax;
            }
            else{ int gk=(Interval<=CurrentLayer)?4:2;
                //gk=2;  // // ///
              int a,b;
              a=abs((PartCrelation+Umin)%gk);
              b=abs((PartCrelation+Umax)%gk);
              MinMayReachEnergy+=(a>b)?b:a;
                //MinMayReachEnergy+=abs((PartCrelation+Umin)%gk);
            }
              PartCrelation=0; //
               Umin=0;     //
               Umax=0;     //
                SumEnergy+=MinMayReachEnergy*MinMayReachEnergy;
                MinMayReachEnergy=0;
        } // interval for cycle end 
        // add

        //for()
    }

if(/*MinMayReachEnergy*/SumEnergy>currentenergy){return /*CurrentLowEnergy*/;}
#endif
    if(CurrentLeft>CurrentRight+2)
    { //cout<<"call111 ";
       //int temp;
        /*temp=*/SequenceRecursion(Sequence,CurrentLeft-1,1+CurrentRight,1+CurrentLayer,SequenceLength);
        //cout <<"call1111";
       /*if(temp<CurrentLowEnergy){ 
        CurrentLowEnergy=temp;
       }*/


       /* temp=*/SequenceRecursion(setbit(Sequence,(CurrentLeft-1)),CurrentLeft-1,1+CurrentRight,1+CurrentLayer,SequenceLength);

        /*if(temp<CurrentLowEnergy){
        CurrentLowEnergy=temp;
       }*/
       //clrbit(Sequence,(CurrentLeft-1));
        /*temp=*/SequenceRecursion(setbit(Sequence,(CurrentRight+1)),CurrentLeft-1,1+CurrentRight,1+CurrentLayer,SequenceLength);
        /*if(temp<CurrentLowEnergy){
        CurrentLowEnergy=temp;
       }*/
       /* temp=*/SequenceRecursion(/*twosetbit(Sequence,(CurrentLeft-1),(CurrentRight+1))*/clrbit(Sequence,CurrentLeft-1),CurrentLeft-1,1+CurrentRight,1+CurrentLayer,SequenceLength);
         
         /*if(temp<CurrentLowEnergy){
        CurrentLowEnergy=temp;
       }*/
    }
    if(CurrentLeft==CurrentRight+2){
        //int temp1;
       /* temp1=*/SequenceRecursion(Sequence,CurrentLeft-1,CurrentRight,1+CurrentLayer,SequenceLength);
       /*if(temp1<CurrentLowEnergy){
        CurrentLowEnergy=temp1;
       } */
       setbit(Sequence,(CurrentLeft-1));
       /*temp1=*/SequenceRecursion(Sequence,CurrentLeft-1,CurrentRight,1+CurrentLayer,SequenceLength);
          /*if(temp1<CurrentLowEnergy){
        CurrentLowEnergy=temp1;
       } */
          
    }



    if(CurrentLeft==CurrentRight+1){
       //count ++;
    double Energy=0;
    int Autocorrelations=0;
   for(int i=1;i<SequenceLength;i++){
       for(int j=0;j<SequenceLength-i;j++){
        //int ii=(getbit(Sequence,j));
       // int jj=(getbit(Sequence,(j+i)));
        if(/*(ii==1)&&(jj==0)||(ii==0)&&(jj==1)*/((getbit(Sequence,j))^(getbit(Sequence,(j+i))))){
            Autocorrelations=Autocorrelations-2;
            //Autocorrelations--;
        }
       /* if(((ii==0)&&(jj==1))){
            //Autocorrelations--;
            //Autocorrelations--;
            Autocorrelations=Autocorrelations-2;
        }*/
        //Autocorrelations++;
        Autocorrelations=Autocorrelations+1;
        //int jj=(unsigned)(getbit(Sequence,(j+i)));
       // if(jj==0){
       //     jj--;
      //  }
          // Autocorrelations=Autocorrelations+(~(getbit(Sequence,j)^getbit(Sequence,(j+i))))*2-1;
          //Autocorrelations=Autocorrelations+ii*jj;
       }
       Energy=Energy+Autocorrelations*Autocorrelations;
       Autocorrelations=0;
   }
  // Energy=Energy/*-SequenceLength*SequenceLength*/;
   if(Energy<currentenergy){

    //CurrentLowEnergy=Energy;
    currentenergy=Energy;
    SequenceLowEnergy=Sequence;
   // cout<<Sequence<<endl;
   }

    } //if
//cout<<Energy<<endl;
   return /*CurrentLowEnergy*/;
}




